package DynamicProgramming;
/**
 * P740删除并获取点数
 * */
public class P740 {
    public static void main(String[] args) {
        P740Test01  p740Test01=new P740Test01();
        int[] a={2,2,3,3,3,4};
        System.out.println(p740Test01.deleteAndEarn(a));
    }
}

/**
 * 动态规划
 * */
class P740Test01{
    public int deleteAndEarn(int[] nums) {
        int length=nums.length;
        //特判
        if(length==0)
            return 0;
        else if(length==1)
            return nums[0];

        //获取数组里面最大值
        int max=Integer.MIN_VALUE;
        for(int n:nums){
            max=Math.max(n, max);
        }
        //建立存储每个数出现次数的数组
        int[] count=new int[max+1];
        for(int n:nums){
            count[n]++;
        }

        //建立动态规划（dp）数组
        int[] dp=new int[max+1];
        //初始化
        //存在一个数的话就是最大
        dp[1]=count[1];


        for(int i=2;i<max+1;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+i*count[i]);
        }

        return dp[max];

    }
}